// https://leetcode.cn/problems/remove-all-adjacent-duplicates-in-string/
package leet1047removealladjacentduplicate

// 思路：
// 1. 使用栈来存储字符
// 2. 遍历字符串中的每个字符
// 3. 如果栈为空，或者栈顶字符与当前字符不同，则将当前字符入栈
// 4. 如果栈顶字符与当前字符相同，则将栈顶字符出栈
// 5. 最后将栈中的字符拼接成字符串返回
// 6. 注意：如果字符串为空，返回空字符串
func RemoveDuplicates(s string) string {
	// 使用切片模拟栈
	stack := []byte{}
	for i := 0; i < len(s); i++ {
		// 如果栈为空，或者栈顶字符与当前字符不同，则将当前字符入栈
		if len(stack) == 0 || stack[len(stack)-1] != s[i] {
			stack = append(stack, s[i])
		} else {
			// 如果栈顶字符与当前字符相同，则将栈顶字符出栈
			stack = stack[:len(stack)-1]
		}
	}
	return string(stack)
}

// 复杂度分析：
// 1. 时间复杂度：O(n)，其中n为字符串的长度。每个字符最多入栈和出栈一次。
// 2. 空间复杂度：O(n)，栈中最多存储n个字符。最坏情况下，字符串中没有重复字符，栈中存储所有字符。
// 3. 注意：如果字符串为空，返回空字符串

// 如果是UTF8编码的字符串，使用[]rune(s)转换为rune切片，
// 这样可以正确处理中文字符和其他多字节字符
func RemoveDuplicatesUTF8(s string) string {
	// 使用切片模拟栈
	stack := []rune{}
	// 遍历字符串中的每个rune
	for _, r := range s {
		// 如果栈为空，或者栈顶字符与当前字符不同，则将当前字符入栈
		if len(stack) == 0 || stack[len(stack)-1] != r {
			stack = append(stack, r)
		} else {
			// 如果栈顶字符与当前字符相同，则将栈顶字符出栈
			stack = stack[:len(stack)-1]
		}
	}
	return string(stack)
}
